//
//  twoPointLookup.c
//  Chapter_1
//
//  Created by hao on 18/3/18.
//  Copyright © 2018年 hao. All rights reserved.
//

#include "twoPointLookup.h"

Position erfen_search(List list, int current, ElementType x);

Position twoPointLookup(List list, ElementType x)
{
    
    int minIndex = 0;
    int maxIndex = list->last;
    // 取中间值, 对比 大于 等于 小于
    int center = (minIndex+maxIndex)*0.5;
    
    // 当minIndex > maxIndex 时表示搜索对比完毕
    while (minIndex <= maxIndex) {
        ElementType currentValue = list->data[center];
        // 等于就跳出循环
        if (currentValue == x) {
            return center;
        }
        // 表示值在右边，最小值等于中点＋1
        if (currentValue < x) {
            minIndex = center+1;
        } else { // 否则向左搜索，最大值等于中点－1
            maxIndex = center-1;
        }
        center = (minIndex+maxIndex)*0.5;
        printf("currentValue = %d \n", currentValue);
    }
    return TPL_NOT_FOUND;
}

// 创建一个线性表
List makeEmptyList()
{
    List list = (List)malloc(sizeof(struct LNode));
    list->last = -1;
    return list;
}

// 返回第k个位置线性表的data
ElementType findKthInList(int k, List list)
{
    if (k > list->last || k < 0) {
        return TPL_NOT_FOUND;
    }
    return list->data[k];
}

// 在线性表中查找第一次出现 x 的值的位置
int findElement(ElementType x, List list)
{
    int i = 0;
    while (i <= list->last && list->data[i] != x) {
        i++;
    }
    if (i > list->last) {
        return TPL_NOT_FOUND;
    }
    return i;
}

// 在序列 i 前插入一个新元素 x
void insertElement(ElementType x, int i, List list)
{
    // 是否已存满
    if (list->last == TPL_MAX_SIZE-1) {
        printf("数据已存满");
        return ;
    }
    // i 必须大于1 且 小于list->last+1
    if (i < 1 || i > list->last+1) {
        printf("插入序号i不正确");
        return ;
    }
    // 在i之后位置的数据向后移动一
    for (int j = list->last; j >= i-1; j--) {
        list->data[j+1] = list->data[j];
    }
    // 为什么放在i－1位置，因为数组是从0开始的，第2个位置就是下标为1
    list->data[i-1] = x;
    list->last++;
}

// 删除指定位置 i 的元素
void deleteElemInList(int i, List list)
{
    // i 必须大于1 且 小于list->last+1, 因为i－1才是数组的下标
    if (i < 1 || i > list->last+1) {
        printf("删除序号i不正确");
        return ;
    }
    //从后往前覆盖即可
    for (int j = i-1; j <= list->last; j++) {
        list->data[j] = list->data[j+1];
    }
    list->last--;
}



